/*
 * Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class Triangle {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int l = triangle.size();
        if(l == 0)
            return 0;
        for(int i = l-1; i > 0; i--)
        {
            for(int j = 0; j < triangle.get(i-1).size(); j++)
            {
                triangle.get(i-1).set(j, triangle.get(i-1).get(j) + 
                    Math.min(triangle.get(i).get(j), triangle.get(i).get(j+1)));
            }
        }
        return triangle.get(0).get(0);
    }
}
